//1.分治-归并排序-排序数组
class Solution {
public:
    vector<int> tmp;
    void merge_sort(vector<int>& nums, int l, int r)
    {
        if(l >= r) return;
        int mid = (l + r) >> 1;
        merge_sort(nums, l, mid);
        merge_sort(nums, mid + 1, r);
        //合并两个有序数组
        int cur1 = l, cur2 = mid + 1, i = l;
        while(cur1 <= mid && cur2 <= r)
        {
            if(nums[cur1] <= nums[cur2]) tmp[i++] = nums[cur1++];
            else tmp[i++] = nums[cur2++];    
        }
        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= r) tmp[i++] = nums[cur2++];
        for(int i = l; i <= r; i++) nums[i] = tmp[i];
    }

    vector<int> sortArray(vector<int>& nums) {
        tmp.resize(nums.size());
        merge_sort(nums, 0, nums.size() - 1); 
        return nums;
    }
};

//2.分治-归并排序-数组中的逆序对
//策略一:统计这个数之前, 有多少个数比我大 --- 数组必须是升序
class Solution {
public:
    int ret = 0;
    vector<int> tmp;

    void merge_sort(vector<int>& nums, int l, int r)
    {
        if(l >= r) return;
        int mid = (l + r) >> 1;
        merge_sort(nums, l, mid);
        merge_sort(nums, mid + 1, r);
        int cur1 = l, cur2 = mid + 1, i = l;
        while(cur1 <= mid && cur2 <= r)
        {
            if(nums[cur1] <= nums[cur2]) tmp[i++] = nums[cur1++];
            else 
            {
                ret += mid - cur1 + 1;
                tmp[i++] = nums[cur2++];
            }
        }
        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= r) tmp[i++] = nums[cur2++];
        for(int i = l; i <= r; i++) nums[i] = tmp[i];
    }

    int reversePairs(vector<int>& nums) {
        tmp.resize(nums.size());
        merge_sort(nums, 0, nums.size() - 1);
        return ret;
    }
};

//策略二:统计这个数之后, 有多少个数比我小 --- 数组必须是降序
class Solution {
public:
    vector<int> tmp;
    int merge_sort(vector<int>& nums, int l, int r)
    {
        if(l >= r) return 0;
        int mid = (l + r) >> 1;
        int ret = 0;
        ret += merge_sort(nums, l, mid);
        ret += merge_sort(nums, mid + 1, r);
        int cur1 = l, cur2 = mid + 1, i = l;
        while(cur1 <= mid && cur2 <= r)
        {
            if(nums[cur1] > nums[cur2]) 
            {
                ret += r - cur2 + 1;
                tmp[i++] = nums[cur1++];
            }
            else 
            {
                tmp[i++] = nums[cur2++];
            }
        }
        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= r) tmp[i++] = nums[cur2++];
        for(int i = l; i <= r; i++) nums[i] = tmp[i];
        return ret;
    }

    int reversePairs(vector<int>& nums) {
        tmp.resize(nums.size());
        return merge_sort(nums, 0, nums.size() - 1);
    }
};